package com.leetcode.sort;

import java.util.Arrays;

/**
 * @program: leetcode  912 题
 * @author: jzhou
 * @date: 2022-11-19 12:16
 * @version: 1.0
 * @description: 快速排序
 **/
public class QuickSort {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    private void quickSort(int[] arr, int left, int right) {

        if (left < right){
            int pivot = findPartition(arr,left,right);
            quickSort(arr, left,pivot - 1);
            quickSort(arr, pivot + 1,right);
        }

    }

    private int findPartition(int[] arr, int left, int right) {
        int partition = arr[left];
        while (left < right){
            while (left < right && partition <= arr[right]){
                right--;
            }
            arr[left] = arr[right];

            while (left < right && partition >= arr[left]){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = partition;
        return left;
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] nums = {5,6,2,3,1};
        quickSort.quickSort(nums,0,nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}
